//package work.rightAnswer;
//
//class WordDictionary {
//
//    Trie root;
//
//    public WordDictionary() {
//        root = new Trie();
//    }
//
//    public void addWord(String word) {
//        root.insert(word);
//    }
//
//    public boolean search(String word) {
//        return dfs(word,0,root);
//    }
//
//    //从index到word.length-1处的单词是否在node中存在
//    public boolean dfs(String word,int index,Trie node) {
//        //查询单词是否存在 有字母或者. 字母限定只能是该字母 .可以是任意字母
//        if(index>=word.length()){
//            return node.isEnd;
//        }
//
//        int ch = word.charAt(index);
//        //判断ch是不是字母
//        if(Character.isLetter(ch)){
//            //是字母，判断当前对应子节点是否存在 与dfs(word,index+1,node.children[ch-'a'])是否为true
//            int num = ch-'a';
//            Trie child = node.children[num];
//            if(child!=null&&dfs(word,index+1,child)){
//                return true;
//            }
//        }else {
//            for (int i = 0; i < 26; i++) {
//                if(node.children[i]!=null&&dfs(word,index+1,node.children[i])){
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//}
//
//class Trie{
//    boolean isEnd;
//    Trie[] children;
//
//    public Trie(){
//        children = new Trie[26];
//        isEnd = false;
//    }
//
//
//    public void insert(String word){
//        Trie node = this;
//        for (int i = 0; i < word.length(); i++) {
//            //遍历word每个字符
//            //1.取出字符c，判断node.children[c-'a']是否为空，如果为空，就新建一个
//            char c = word.charAt(i);
//            if(node.children[c-'a']==null){
//                node.children[c-'a'] = new Trie();
//            }
//            //2.遍历到子节点
//            node = node.children[c-'a'];
//        }
//        //3.将末节点的isEnd设置为true
//        node.isEnd = true;
//    }
//
//
//}